/**
 * 顺序表实现栈
 */
#include <iostream>
#include <stdexcept>

using namespace std;

// 栈内元素定制化，模板实现
template <typename T>
class Stack
{
private:
    T *data;       // T类型的数组
    int size;      // 元素个数
    int capacity;  // 容量
    void resize(); // 扩容函数

public:
    Stack() : data(new T[10]), size(0), capacity(10) {}
    ~Stack();

    // 入
    void push(T element);
    // 出
    T pop();
    // 获取栈顶元素
    T top() const;
    // 获取元素个数
    int getSize() const;
};

template <typename T>
void Stack<T>::resize()
{
    int nNewCapacity = capacity * 2;
    T *newData = new T[nNewCapacity];
    for (int i = 0; i < size; ++i)
    {
        newData[i] = data[i];
    }
    delete[] data;
    data = newData;
    capacity = nNewCapacity;
}

template <typename T>
Stack<T>::~Stack()
{
    delete[] data;
}

template <typename T>
void Stack<T>::push(T element)
{
    if (size == capacity)
    {
        resize();
    }
    data[size++] = element;
}

template <typename T>
T Stack<T>::pop()
{
    if (size == 0)
    {
        throw std::underflow_error("Stack is empty");
    }
    return data[--size];
}

template <typename T>
T Stack<T>::top() const
{
    if (size == 0)
    {
        throw std::underflow_error("Stack is empty");
    }
    return data[size - 1];
}

template <typename T>
int Stack<T>::getSize() const
{
    return size;
}

int main()
{
    Stack<int> st;
    st.push(4);
    st.push(33);
    st.push(16);
    st.push(78);
    st.push(15);
    cout << st.top() << endl;
    cout << st.getSize() << endl;
    st.pop();
    cout << st.top() << endl;
    cout << st.getSize() << endl;
    st.pop();
    cout << st.top() << endl;
    cout << st.getSize() << endl;
    return 0;
}